package dynamicProgramming;

/**
 * @author zxc
 * @date 2023/01/31 11:03
 **/

/**
 * 题目 ：最长有效括号
 * 题目详述 ：
 * 给你一个只包含 '(' 和 ')' 的字符串，找出最长有效（格式正确且连续）括号子串的长度。
 *
 * 提示：
 * 0 <= s.length <= 3 * 104
 * s[i] 为 '(' 或 ')'
 */
public class LongestValidParenthese {
    public static void main(String[] args) {
        System.out.println(longestValidParentheses("()(()"));
    }
    /**
     * 思路 ：
     * 要求解最长有效（格式正确且连续）括号子串的长度，即选择使用动态规划来解决;
     *
     * 假设f(i)为长度为i字符串的最长有效括号子串长度;
     * 状态转移方程 :
     * （1）若是第i个字符为"("的话，即 f(i) = f(i-1);
     * （2）若是第i个字符为")"的话，
     * a.若是第i-1个字符不为"("（即，不构成有效括号的话）,f(i) = f(i-1);
     * b.若是第i-1个字符为"("的话，即f(i) = f(i-2) + 1;
     * （3）考虑特殊情况 ：
     * f(0) == 0 && f(1) == 0(即，当字符串长度为0/1时，必然不可能构成有效括号;)
     *
     * @param s
     * @return
     */
    public static int longestValidParentheses(String s) {
        int len = s.length();
        int[] temp = new int[len + 1];
        temp[0] = 0;
        if(len > 0){
            temp[1] = 0;
        }
        // "()(()"
        for(int i = 1; i < len ; i++){
            if(s.charAt(i) == '('){
                temp[i + 1] = temp[i];
            }
            else {
                int k = 1;
                int rightNumber = 1;
                int sum = 0;

                while(k <= i && s.charAt(i - k) == ')'){
                    k++;
                    rightNumber++;
                }
                while(k <= i && s.charAt(i - k) == '('){
                    k++;
                    if(rightNumber > 0){
                        sum++;
                    }
                    rightNumber--;
                }

                temp[i + 1] = temp[i + 1 - k];
                if(rightNumber == 0){
                    temp[i + 1] += 2 * sum;
                }
            }
        }
        return temp[len];
    }
}
